package com.da.javatest.niuke.jianzhi;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author chenlida
 * @date 2020/10/22 19:27
 * https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?
 * tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C40Solution {
    public static void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        Arrays.sort(array);
        Stack<Integer> stack = new Stack<>();
        for (int i : array) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                if (stack.peek() == i) {
                    stack.pop();
                } else {
                    stack.push(i);
                }
            }
        }
        num1[0] = stack.pop();
        num2[0] = stack.pop();
    }

    public void FindNumsAppearOnce2(int[] array, int num1[], int num2[]) {
        int temp = array[0];
        //首先把数组中的数字全部进行异或
        for (int i = 1; i < array.length; i++) {
            temp ^= array[i];
        }
        //把异或结果的最后一位1的那位找出来
        temp &= -temp;
        //以这一位是否为1或者0作为分类标准进行分类
        for (int val : array) {
            if ((val & temp) == 0) {
                num1[0] ^= val;
            } else {
                num2[0] ^= val;
            }
        }

    }

    public static void main(String[] args) {
        FindNumsAppearOnce(new int[] {2, 4, 3, 6, 3, 2, 5, 5}, new int[1], new int[1]);
    }
}
